package linkedtable;

import org.junit.Test;
import util.List.ListNode;

import java.util.LinkedList;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-09-02 19:50
 */
public class LCR025_addTwoNumbers {
    @Test
    public void test() {
        ListNode l1 = ListNode.createLinkedList(new int[]{5});
        ListNode l2 = ListNode.createLinkedList(new int[]{5});
        addTwoNumbers(l1, l2);
    }

    // 思路：分别将两个链表分别入栈
    LinkedList<Integer> stack1 = new LinkedList<>();
    LinkedList<Integer> stack2 = new LinkedList<>();

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        while (l1 != null) {
            stack1.addLast(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.addLast(l2.val);
            l2 = l2.next;
        }

        int sum = 0;
        int carry = 0;
        int ge = 0;
        ListNode dump = new ListNode(), cur = dump;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            int a = stack1.isEmpty() ? 0 : stack1.removeLast();
            int b = stack2.isEmpty() ? 0 : stack2.removeLast();
            sum = a + b + carry;
            carry = sum / 10;
            ge = sum % 10;
            cur = new ListNode(ge);
            // 头插法
            cur.next = dump.next;
            dump.next = cur;
        }

        if (carry == 1) {
            cur = new ListNode(carry);
            // 头插法
            cur.next = dump.next;
            dump.next = cur;
        }

        return dump.next;
    }
}
